package org.ala.everyday;

import java.sql.Array;
import java.util.*;

/**
 * 给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
 *
 * 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
 * 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
 *
 * 求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
 * 输出：2
 * 解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
 * 示例 2：
 *
 * 输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
 * 输出：-1
 *
 *
 * 提示：
 *
 * 1 <= routes.length <= 500.
 * 1 <= routes[i].length <= 105
 * routes[i] 中的所有值 互不相同
 * sum(routes[i].length) <= 105
 * 0 <= routes[i][j] < 106
 * 0 <= source, target < 106
 *
 * @author ala
 * @date 2024-09-17 00:37
 */
public class Q815 {
    public static void main(String[] args) {
        Q815 q = new Q815();

//        int[][] routes = {{1,2,7}, {3,6,7}};
//        int source = 1, target = 6;

        int[][] routes = {{1,2,7}, {3,6,7}};
        int source = 8, target = 6;

//        int[][] routes = {{7,12},{4,5,15},{6},{15,19},{9,12,13}};
//        int source = 15, target = 12;

//        int[][] routes = {{0,1,6,16,22,23},{14,15,24,32},{4,10,12,20,24,28,33},{1,10,11,19,27,33},{11,23,25,28},{15,20,21,23,29},{29}};
//        int source = 4, target = 21;

        System.out.println(q.numBusesToDestination(routes, source, target));
    }
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {return 0;}
        return V1(routes, source, target);
    }
    static int MAX = (int)1e6;
    /**
     *  1）每个站点有哪些公交车，每个公交车有哪些站点
     *  2）从起点出发，找到经过起点的公交车，找到这些公交车的站点
     *      这些站点是第一轮bfs能到达的（乘坐1次）
     *  3）遍历经过这些站点的公交车，遍历这些公交车的站点
     *      这些站点是第二轮bfs能到达的（乘坐2次）
     *  4）若某次遍历的站点就是终点，则返回乘坐次数
     */
    protected int V1(int[][] routes, int source, int target) {
        //  每个站点经过哪些公交车，每个公交车经过哪些站点
        sbm = new HashMap<>();
        bsm = new HashMap<>();
        max = 0;
        for (int i = 0 ; i < routes.length ; i++) {
            int[] rs = routes[i];
            for (int r : rs) {
                sbm.computeIfAbsent(r, k -> new ArrayList<>()).add(i);
                bsm.computeIfAbsent(i, k -> new ArrayList<>()).add(r);
                max = Math.max(max, r);
            }
        }
        if (!sbm.containsKey(source) || !sbm.containsKey(target)) {return -1;}

        //  bfs
        return bfs(Arrays.asList(source), 0, target, new boolean[routes.length]);
    }
    protected Map<Integer, List<Integer>> sbm, bsm;
    protected int max;
    protected int bfs(List<Integer> roots, int depth, int target, boolean[] vis) {
        //  找到途径roots的所有公交车的所有途径站，作为下次遍历的root
        List<Integer> nexts = new ArrayList<>();
        boolean[] _vis = new boolean[max + 1];
        for (int r : roots) {
            if (r == target) { return depth; }

            List<Integer> bus = sbm.get(r);
            for (int b : bus) {
                if (vis[b]) {continue;}
                vis[b] = true;
                List<Integer> sts = bsm.get(b);
                for (int s : sts) {
                    if (_vis[s]) {continue;}
                    _vis[s] = true;
                    nexts.add(s);
                }
            }
        }

        if (nexts.isEmpty()) {return -1;}
        else {return bfs(nexts, depth + 1, target, vis);}
    }

}
